public class Offer12 {

    int[][] directArr = new int[][]{new int[]{0, 1}, new int[]{1, 0}, new int[]{0, -1}, new int[]{-1, 0}};

    char[][] board;
    String word;
    int m, n;

    private boolean search(boolean[][] isBeen, int i, int j, int loc){
        if(word.charAt(loc) != board[i][j]){
            return false;
        }
        if(loc == word.length() - 1){
            return true;
        }
        isBeen[i][j] = true;
        for (int[] direct : directArr) {
            int newI = i + direct[0], newJ = j + direct[1];
            if(0 <= newI && newI < m &&
               0 <= newJ && newJ < n &&
               !isBeen[newI][newJ] &&
               search(isBeen, newI, newJ, loc + 1)){
                return true;
            }
        }
        isBeen[i][j] = false;
        return false;
    }

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.m = board.length;
        this.n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(search(new boolean[m][n], i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }
}
